package day230415;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/4/16 16:47
 * 迷宫问题
 */
public class Main {

    // 用于存储坐标的内部类
    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "(" + x + "," + y + ")";
        }
    }

    static int[] dirX = {1, -1, 0, 0}; // 方向数组
    static int[] dirY = {0, 0, 1, -1}; // 方向数组

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 录入行列和地图
        int row = scan.nextInt();
        int col = scan.nextInt();
        int[][] map = new int[row][col];
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                map[i][j] = scan.nextInt();
            }
        }
        // 求最短路径
        List<Node> path = new ArrayList<>();
        List<Node> minPath = new ArrayList<>();
        boolean[][] flag = new boolean[row][col];
        findMinPath(map, row, col, 0, 0, flag, path, minPath);
        // 打印结果
        for (Node node : minPath) {
            System.out.println(node);
        }
        scan.close();
    }

    /**
     * 用于寻找地图的最短路
     * @param map 存储地图 0 表示可达 1 表示障碍
     * @param row 行
     * @param col 列
     * @param x 坐标
     * @param y 坐标
     * @param flag 标记是否被走过
     * @param path 记录路径
     * @param minPath 记录最短路径
     */
    private static void findMinPath(int[][] map, int row, int col, int x, int y, boolean[][] flag, List<Node> path, List<Node> minPath) {
        // 判断是否越界
        if (x < 0 || x == row || y < 0 || y == col || flag[x][y] || map[x][y] == 1) {
            return;
        }
        // 寻路
        path.add(new Node(x, y));
        flag[x][y] = true;
        // 判断是否到达终点
        if (x == row - 1 && y == col - 1) {
            // 到达终点, 则比较看是否路径更短, 更新最短路
            if (minPath.size() == 0 || path.size() < minPath.size()) {
                minPath.addAll(path);
            }
        }
        // 四个方向继续深搜
        for (int i = 0; i < 4; i++) {
            findMinPath(map, row, col, x + dirX[i], y + dirY[i], flag, path, minPath);
        }
        // 回退
        path.remove(path.size() - 1);
        flag[x][y] = false;
    }
}
